Design a Leaderboard class, which has 3 functions:
addScore(playerId, score): Update the leaderboard by addingscoreto the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the givenscore.top(K): Return the score sum of the topKplayers.reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.
Initially, the leaderboard is empty.
Example 1:
Input: ["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"] [[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]] Output: [null,null,null,null,null,null,73,null,null,null,141] Explanation: Leaderboard leaderboard = new Leaderboard (); leaderboard.addScore(1,73); // leaderboard = [[1,73]]; leaderboard.addScore(2,56); // leaderboard = [[1,73],[2,56]]; leaderboard.addScore(3,39); // leaderboard = [[1,73],[2,56],[3,39]]; leaderboard.addScore(4,51); // leaderboard = [[1,73],[2,56],[3,39],[4,51]]; leaderboard.addScore(5,4); // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]]; leaderboard.top(1); // returns 73; leaderboard.reset(1); // leaderboard = [[2,56],[3,39],[4,51],[5,4]]; leaderboard.reset(2); // leaderboard = [[3,39],[4,51],[5,4]]; leaderboard.addScore(2,51); // leaderboard = [[2,51],[3,39],[4,51],[5,4]]; leaderboard.top(3); // returns 141 = 51 + 51 + 39;
Constraints:
1 <= playerId, K <= 10000- It's guaranteed that
Kis less than or equal to the current number of players. 1 <= score <= 100- There will be at most
1000function calls.
Average Rating: 4.50 (12 votes)
Overview
There are a lot of implementations for this particular problem out there. The problem statement is pretty straightforward on the surface:
- We need to maintain a list of
playerIdtoscoremappings. - Whenever required, obtain the top
Kscores, add them up, and return them. - Finally, reset the score for a particular player.
We will start with the most basic, brute-force implementations for this problem and then move on to slightly complex implementations. To understand, what these complicated implementations will be using, we need to see the basic requirement of this problem.
We have a dynamically updating list of values and we need to be able to extract the top-k elements from that list.
Whenever we have such a problem statement which requires us to obtain the top-K values from a list which is dynamically updating, relying on a priority-queue seems like a good bet. A heap is one of the best data structures for handling such a requirement. So, we will be looking at a solution that makes use of the heap data structure.
Additionally, we will be looking at a binary search tree based solution. Although the heap is a great data structure for finding the top-K elements from a list without having to actually sort the list, it is not great at find-and-update kind of operations. General rule of thumb with the heap data structure is to use lazy-updates rather than having to traverse and update the entries themselves. We won't get a deterministic performance if we resort to lazy score updates here because we don't know the number of update operations and hence, the size of the heap can continue to grow if we have millions of score updates and no top-K function calls (or proportionally lower).
Approach 1: Brute Force
The brute-force approach is pretty straightforward in the sense that we will maintain a dictionary of playerId as the key and the score as the dictionary. Then, for each top operation, we will simply obtain all the values from the dictionary, sort them, and the obtain the top K elements.
Algorithm
- Initialize a dictionary
scoresthat will use theplayerIdas the key andscoreas the value. - addScore ~
- Simply update the dictionary with the new score for the player.
- If the player doesn't exist, initialize the score to
score
- top ~
- Obtain a list of all the values from the dictionary.
- Sort the list in
reverseorder. - Sum up the first
Kvalues from the sorted list.
- reset ~
- Delete the entry containing the
playerId - Note that we can also set the value (score) to
0. The only disadvantage of this is that we will be sorting evenresetplayers in thetopfunction. This doesn't matter much for smaller test cases though.
- Delete the entry containing the
Implementation
Complexity Analysis
-
Time Complexity:
- O(1) for
addScore. - O(1) for
reset. - O(NlogN) for
topwhere N represents the total number of players since we sort all of the player scores and then take the topKfrom the sorted list.
- O(1) for
-
Space Complexity:
- O(N) used by the
scoresdictionary and also by the new list formed using the dictionary values in thetopfunction.
- O(N) used by the
Approach 2: Heap for top-K
This is a slight modification to the previous approach in that instead of sorting the list of the values, we will be making use of a min-heap to find the top-K values. This is a slightly modified version of the previous implementation.
Algorithm
- Initialize a dictionary
scoresthat will use theplayerIdas the key andscoreas the value. - addScore ~
- Simply update the dictionary with the new score for the player.
- If the player doesn't exist, initialize the score to
score
- top ~
- Initialize a new min-heap,
scoreHeap. - Iterate over the first
Kvalues in the dictionary and add them to the heap. - Then, for the rest of the N−K values, we will simply do the following. We will add the new value to the heap, and pop the smallest value from the heap. In doing this, we maintain the size of the heap to
Kand also remove the smaller of the two values. - We do this for all of the N−K values and then, simply add up all the values remaining in the heap since those would be the largest
Kvalues left.
- Initialize a new min-heap,
- reset ~
- Delete the entry containing the
playerId - Note that we can also set the value (score) to
0. The only disadvantage of this is that we will be sorting evenresetplayers in thetopfunction. This doesn't matter much for smaller test cases though.
- Delete the entry containing the
Implementation
Complexity Analysis
-
Time Complexity:
- O(1) for
addScore. - O(1) for
reset. - O(K)+O(NlogK) = O(NlogK). It takes O(K) to construct the initial heap and then for the rest of the N−K elements, we perform the
extractMinandaddoperations on the heap each of which take (logK) time.
- O(1) for
-
Space Complexity:
- O(N+K) where O(N) is used by the
scoresdictionary and O(K) is used by the heap.
- O(N+K) where O(N) is used by the
Approach 3: Using a TreeMap / SortedMap
This approach is inspired by this discussion thread. Here we will try to improve on the overall time complexity of the top function at the expense of the time complexity of the addScore function. As discussed before, a heap doesn't have any properties that aid in search. At the end of the day, it is simply list of elements with certain properties associating them. However, these properties do not enhance the searchability of the data structure as a whole. We can definitely do enhancements where we maintain references to nodes in the heap, in a dictionary and then use those references for making updates. However, we will be looking at the TreeMap data structure (java) which uses the balanced-binary-search tree instead.
The great advantage we get with a balanced BST is that the search/add/remove operations are all bounded by a logarithmic complexity in terms of the number of elements in the tree. This is achievable due to the structure of the tree and the relationship between the subtrees and a root.
Algorithm
- Initialize a dictionary
scoresthat will use theplayerIdas the key andscoreas the value. - Initialize a TreeMap (java) or a SortedMap (python) called
sortedScoreMap. The way this would be structured is that the key would be a score and the value would be the number of players that have this score. Imagine this being represented as a balanced BST with the keys being used for arranging the tree. We need thetopfunction to use the scores and so, we use them as the key. - addScore ~
- Note the old score for the player. Let it be called
oldScore. - Update the value of
oldScoreinsortedScoreMapTreeMap. If the value has reached0, remove the score entry. - Simply update the dictionary with the new score for the player.
- Add the updated value to the
sortedScoreMapas well by incrementing the value by 1 i.e. one more player has this score. - If the player doesn't exist, initialize the score to
score.
- Note the old score for the player. Let it be called
- top ~
- Iterate over all the keys in the
sortedScoreMap. Note that since the data structure is a BST, an inorder traversal of the keys would return them in the sorted order. We don't need to sort them again. Hence, we will simply iterate over the keys and pick the firstK. Also, we have arranged the tree with each score mapped to how many players have that score. So there are no duplicates in the tree. - Pick the first
Kentries i.e. firstKvalues.- For each key, multiply
(key * value)and add it to the total sum. - Also, reduce the counter counting down to
Kbyvalue.
- For each key, multiply
- Iterate over all the keys in the
- reset ~
- Note the old score for the player. Let it be called
oldScore. - Update the value of
oldScoreinsortedScoreMapTreeMap. If the value has reached0, remove the score entry. - Delete the entry containing the
playerId.
- Note the old score for the player. Let it be called
Implementation
Note that we are using SortedDict in Python. This is an external, apache licensed package that is supported by the Leetcode platform. You can read more about it here. We don't have a way to construct a reverse SortedDict in Python and hence, we negate the scores before adding them to the dict (TreeMap like data structure) so that the normal in-order traversal would give us the scores in the reverse order i.e. descending order.
Complexity Analysis
-
Time Complexity:
- O(logN) for
addScore. This is because each addition to the BST takes a logarithmic time for search. The addition itself once the location of the parent is known, takes constant time. - O(logN) for
resetsince we need to search for the score in the BST and then update/remove it. Note that this complexity is in the case when every player always maintains a unique score. - It takes O(K) for our
topfunction since we simply iterate over the keys of the TreeMap and stop once we're done consideringKscores. Note that if the data structure doesn't provide a natural iterator, then we can simply get a list of all the key-value pairs and they will naturally be sorted due to the nature of this data structure. In that case, the complexity would be O(N) since we would be forming a new list.
- O(logN) for
-
Space Complexity:
- O(N) used by the
scoresdictionary. Also, if you obtain all the key-value pairs in a new list in thetopfunction, then an additional O(N) would be used.
- O(N) used by the
In the Approach 3 there is no need to iterate over times, you can calculate how many players with score key you can take: can_take = min(K - count, times). And then sum += can_take * key.
May 24, 2021 1:41 AM
for Approach #3, please fix the summing part. Can sum up using count of remaining v/s needed:
class Leaderboard {
Map<Integer, Integer> scores;
TreeMap<Integer, Integer> sortedScores;
public Leaderboard() {
this.scores = new HashMap<Integer, Integer>();
this.sortedScores = new TreeMap<>(Collections.reverseOrder());
}
public void addScore(int playerId, int score) {
// The scores dictionary simply contains the mapping from the
// playerId to their score. The sortedScores contain a BST with
// key as the score and value as the number of players that have
// that score.
if (!this.scores.containsKey(playerId)) {
this.scores.put(playerId, score);
this.sortedScores.put(score, this.sortedScores.getOrDefault(score, 0) + 1);
} else {
// Since the current player's score is changing, we need to
// update the sortedScores map to reduce count for the old
// score.
int preScore = this.scores.get(playerId);
int playerCount = this.sortedScores.get(preScore);
// If no player has this score, remov it from the tree.
if (playerCount == 1) {
this.sortedScores.remove(preScore);
} else {
this.sortedScores.put(preScore, playerCount - 1);
}
// Updated score
int newScore = preScore + score;
this.scores.put(playerId, newScore);
this.sortedScores.put(newScore, this.sortedScores.getOrDefault(newScore, 0) + 1);
}
}
public int top(int K) {
int sum = 0;
for (Map.Entry<Integer, Integer> e: this.sortedScores.entrySet()) {
// Number of players that have this score.
int times = Math.min(K, e.getValue());
sum += times*e.getKey();
K -= times;
// Found top-K scores, break.
if (K <= 0) {
break;
}
}
return sum;
}
public void reset(int playerId) {
int preScore = this.scores.get(playerId);
this.sortedScores.put(preScore, this.sortedScores.get(preScore) - 1);
if (this.sortedScores.get(preScore) == 0) {
this.sortedScores.remove(preScore);
}
this.scores.remove(playerId);
}
}
I would love for the authors to also consider a solution based on Doubly LinkedList + HashMap!
My implementation beats 100% [Java], which was a surprise.
Heavily inspired by LRU Cache problem!
https://leetcode.com/problems/design-a-leaderboard/discuss/1214603/Java-beats-100-solution-Double-LinkedList-%2B-HashMap
December 18, 2020 1:52 AM
The time complexity to retrieve next operation is actually O(logn) in Java, here is the code from JDK:
/**
* Base class for TreeMap Iterators
*/
abstract class PrivateEntryIterator implements Iterator {
Entry<K,V> next;
Entry<K,V> lastReturned;
int expectedModCount;
PrivateEntryIterator(Entry<K,V> first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
/**
* Returns the successor of the specified Entry, or null if no such.
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* Returns the predecessor of the specified Entry, or null if no such.
*/
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.left != null) {
Entry<K,V> p = t.left;
while (p.right != null)
p = p.right;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}
Thus the topK method's time complexity is still actually O(KlogN) in Java, though maybe we can implement the above operations in amortized O(1) time by inorder traversal, but the space complexity would suffer.
The given solutions for Python are pretty trash. For example, the first solution uses defaultdict() but not defaultdict(int). Why? If you use defaultdict(int), then
def addScore(self, playerId: int, score: int) -> None:
if playerId not in self.scores:
self.scores[playerId] = 0
self.scores[playerId] += score
can be simplified to
def addScore(self, playerId: int, score: int) -> None:
self.scores[playerId] += score
Then in the second solution you do
res = 0
while heap:
res += heapq.heappop(heap)
This is so stupid, just do sum(heap). Calling heappop each time forces the heap to switch stuff around internally to maintain the heap invariant.
December 10, 2020 12:05 PM
I think the time complexity of top operation in Approach 3 is K logN. if every player has unique score then we pop the K times. each pop will result in rebalance of N-i items. where i from 1 to K
You don't have any submissions yet.
xxxxxxxxxxclass Leaderboard {public: Leaderboard() { } void addScore(int playerId, int score) { } int top(int K) { } void reset(int playerId) { }};/** * Your Leaderboard object will be instantiated and called as such: * Leaderboard* obj = new Leaderboard(); * obj->addScore(playerId,score); * int param_2 = obj->top(K); * obj->reset(playerId); */